package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main() {
	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 3,
			},
			Right: &TreeNode{
				Val: 4,
			},
		},
		Right: &TreeNode{
			Val: 5,
			Left: &TreeNode{
				Val: 6,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	}
	subRoot := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
		},
		Right: &TreeNode{
			Val: 5,
		},
	}
	fmt.Println(isSubTree(root, subRoot))
}

func isSubTree(root *TreeNode, subRoot *TreeNode) bool {
	if subRoot == nil {
		return false
	}
	if root == nil {
		return false
	}

	return isSameTree(root, subRoot) || isSubTree(root.Left, subRoot) || isSubTree(root.Right, subRoot)

}

func isSameTree(root *TreeNode, subRoot *TreeNode) bool {
	if subRoot == nil {
		return true
	}
	if root == nil {
		return false
	}
	return root.Val == subRoot.Val && isSameTree(root.Left, subRoot.Left) && isSameTree(root.Right, subRoot.Right)
}
